1267K - Key Storage - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;
const int N=25;
long long c[N][N];
int cnt[N];
int main(){
	int T; scanf("%d",&T);
	c[0][0]=1;
	for(int i=1;i<21;++i){
		c[i][0]=1;
		for(int j=1;j<=i;++j) c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	while(T--){
		memset(cnt,0,sizeof(cnt));
		long long x;
		scanf("%lld",&x);
		int id=2;
		while(x) ++cnt[x%id],x/=id,++id;
		--id;
		int k=id;
		long long ans=1,i=0,ans1=1;
		while(id>0){
			--id;
			++i;
			if(id==0) --i;
			ans*=c[i][cnt[id]];
			i-=cnt[id];
		}
		id=k-1;
		--cnt[0];
		if(cnt[id]==0){
			i=0;
			while(id>0){
				--id;
				++i;
				if(id==0) --i;
				ans1*=c[i][cnt[id]];
				i-=cnt[id];
			}
		}
		else ans1=0;
		ans-=ans1;
		--ans;
		printf("%lld\n",ans);
	}
	return 0;
}